題目描述為: 給定一個整數 n, 要判斷是否為完美數。
其中完美數定義為除了本身以外的所有因數和=自己本身。
題目有補充說明 n 的大小不超過 10^8。
例子 1: n=28,output=true。 (28=1+2+4+7+14)
設輸入的數字為 N,且 N>0。 我們可以求出所有 N 的因數,並累加起來,最後判斷是否滿足完美數要求。
參考程式碼
func checkPerfectNumber(num int) bool {
if num<=1{
return false
}
sum:=1
tmp:=0
for i:=2;i*i<num;i++{
if num%i==0{
sum+=i
tmp=num/i
if tmp!=i{
sum+=tmp
}
if sum>num{
return false
}
}
}
if sum!=num{
return false
}
return true
}
方法 1 按照完美數定義處理此問題。此外,要判斷一個數字是否為完美數尚可利用一些數學性質。
而在題目限定範圍內的完美數總共只有 6,8,496,8128,33550336 共 5 個。
我將解法加上簡單的測試,上傳程式碼到此。
數學上專門研究整數性質的分支為數論,關於質數的研究也非常豐富,在密碼學上也有諸多應用。
而質數定理描述了質數在自然數中的分布情形,而著名的黎曼猜想即是與質數分布相關的數學問題之一。
這系列挑選的題目偏向數學相關,是出自個人偏好,在此活動中我們也介紹了許多主題如: 複雜度/Hash法/遞迴/bit operation/tree/in-place/...等等,並安排了數道同類型的題目來練習。而最後一天選擇該主題做為一個 perfect ending,在過程中收穫很多,有機會也會繼續嘗試。